package greedy

import (
	// "fmt"
	"math"
)

//给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
// 子数组 是数组中的一个连续部分。
func maxSubArray(nums []int) int {
	// 如果当前元素是负值，那么对整体的和是负面影响
	// 但是也不能直接就在负值处停下，因为后面可能有正值将其对冲
	// // 先计算整体的sum
	// sum:=0
	// for _,v := range nums {
	// 	sum += v
	// }
	// sum 相当于一个基准值了，结果只能>=sum
	var res int = math.MinInt64
	// 当前连续和为负数，立即停止，从下一个数开始重新计算
	var curSum int 
	for i:=0;i<len(nums);i++{
		curSum += nums[i]
		// fmt.Println(curSum)
		if curSum > res {
			res = curSum
		}
		if curSum <= 0 {
			curSum = 0
			// continue
		}
	}
	return res
}

// class Solution {
// 	public:
// 		int maxSubArray(vector<int>& nums) {
// 			if (nums.size() == 0) return 0;
// 			vector<int> dp(nums.size(), 0); // dp[i]表示包括i之前的最大连续子序列和
// 			dp[0] = nums[0];
// 			int result = dp[0];
// 			for (int i = 1; i < nums.size(); i++) {
// 				dp[i] = max(dp[i - 1] + nums[i], nums[i]); // 状态转移公式
// 				if (dp[i] > result) result = dp[i]; // result 保存dp[i]的最大值
// 			}
// 			return result;
// 		}
// 	};